import numpy as np

def fft(x):
    N = len(x)
    if N <= 1:
        return x
    else:
        even = fft(x[0::2])
        odd = fft(x[1::2])
        T = [np.exp(-2j * np.pi * k / N) * odd[k] for k in range(N // 2)]
        return [even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)]

# 输入长度是2的n(n属于正整数)次方的【数组】
x = np.array([1,1,1,1,1,1,1,1])
result = fft(x)

# 输出结果
print("原始序列：")
print(x)

print("傅里叶变换结果：")
print(result)
